#include <vector>
#include <stdio.h>
#include <iostream>
#include <stack>
#include <map>
#include <string>
#include <iterator>
#include <stdlib.h>     /* srand, rand */
#include <time.h>       /* time */
#include <algorithm>  // sort
#include <ctime>      // clock

using namespace std;

/*
 * Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.
 * Known conditions:
 * Array: nums, start point: s，end point: e，sub slice number: m
 * v{7,2,5,10,8}
 *
 * Want: max sum of each sub slice
 * 
 * 1. recursively caculate the sums of each sub slice
 * 1.1 [7], [2,5,10,8]
 *    | 1 | | m - 1  | max({7}, {2,5,10,8}}
 * 1.2 [2,5,10,8] -> [2], [2,10,8]
 *
 * 2. the sum of a sub slice should be between 2(split into 5 slices) and 32(split into 1 slice)
 * if the minimium sum is 17, how many slices it can be split into?
 * 7 + 2 + 5 < 17; 7 + 2 + 5 + 10 > 17
 * so if the sum is 17((2+32)/2), the possible sub slices are [7,2,5],[10],[8]
 * which means we can split the array into 3 slices
 * now let's consider the relationship of possible number of sub slices and our goal
 * if the goal is 3, we know it is OK, but how about we narrow down the sum?
 * let's see (2+17)/2
 * the slices should be [7,2],[5],[10],[8], which means 9 is smaller than our goal
 * then (9+17)/2, the slices are [7,2],[5],[10],[8], increase left
 * then (13+17)/2+1, -> [7,2,5],[10],[8], decrease right
 * then (13+16)/2, -> [7,2,5],[10],[8], decrease right
 * then (13+14)/2, -> [7,2,5],[10],[8], decrease right
 */

int helper1(vector<int>& nums, int s, int e, int m, vector<vector<vector<int>>>& memo) {
    if (memo[s][e][m] != 0) return memo[s][e][m];
    int result;
    vector<int> results;
    int i;
    if (m == 1) {
        result = accumulate(nums.begin()+s, nums.begin()+e, 0);
        goto out;
    }
    if (m == e - s) {
        result = *max_element(nums.begin()+s, nums.begin()+e);
        goto out;
    }
    for (i = s+1; i < e - (m - 2); ++i) {
        results.push_back(max(helper1(nums, s, i, 1, memo), helper1(nums, i, e, m - 1, memo)));
    }
    result =  *min_element(results.begin(), results.end());
out:
    memo[s][e][m] = result;
    return result;
}

int solution1(vector<int>& nums, int m) {
    vector<int> results;
    int len = nums.size();
    vector<vector<vector<int>>> memo(len, vector<vector<int>>(len+1, vector<int>(m+1, 0)));
    return helper1(nums, 0, len, m, memo);
}

int helper2(vector<int>& nums, int s, int e, int m) {
    int result;
    vector<int> results;
    int i;
    if (m == 1) {
        result = accumulate(nums.begin()+s, nums.begin()+e, 0);
        goto out;
    }
    if (m == e - s) {
        result = *max_element(nums.begin()+s, nums.begin()+e);
        goto out;
    }
    for (i = s+1; i < e - (m - 2); ++i) {
        results.push_back(max(helper2(nums, s, i, 1), helper2(nums, i, e, m - 1)));
    }
    result =  *min_element(results.begin(), results.end());
out:
    return result;
}

int solution2(vector<int>& nums, int m) {
    vector<int> results;
    int len = nums.size();
    return helper2(nums, 0, len, m);
}

bool can_split(vector<int>& nums, int m, int sum) {
	int cnt = 1, curSum = 0;
	for (int i = 0; i < nums.size(); ++i) {
		curSum += nums[i];
		if (curSum > sum) {
			curSum = nums[i];
			++cnt;
			if (cnt > m) return false;
		}
	}
	return true;
}

int solution3(vector<int>& nums, int m) {
	int left = 0, right = 0;
	for (int i = 0; i < nums.size(); ++i) {
		left = max(left, nums[i]);
		right += nums[i];
	}
	while (left < right) {
		int mid = left + (right - left) / 2;
		if (can_split(nums, m, mid)) right = mid;
		else left = mid + 1;
	}
	return right;
}

int main() {
    vector<int> v{7,2,5,10,8,4,11,6,12,3,9,14,17,19,1};
    //vector<int> v{7, 2, 5};
    int result;
    clock_t c_start = clock();
    for (int i = 0; i < 10000; ++i) {
        result = solution1(v, 6);
    }
    cout << "solution1: " << result << " - " << float( clock () - c_start ) /  CLOCKS_PER_SEC << endl;
    c_start = clock();
    for (int i = 0; i < 10000; ++i) {
        result = solution2(v, 6);
    }
    cout << "solution2: " << result << " - " << float( clock () - c_start ) /  CLOCKS_PER_SEC << endl;
    c_start = clock();
    for (int i = 0; i < 10000; ++i) {
        result = solution3(v, 6);
    }
    cout << "solution3: " << result << " - " << float( clock () - c_start ) /  CLOCKS_PER_SEC << endl;
}

